public class Solution494 {
    /**
     * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。
     * 现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
     * <p>
     * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
     */
    int sum = 0;

    public int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0) return 0;
        find(nums, S, 0, 0);
        return sum;
    }

    public void find(int[] nums, int s, int idx, int cur) {
        if (idx == nums.length) {
            if (cur == s) sum++;
        } else {
            find(nums, s, idx + 1, cur + nums[idx]);
            find(nums, s, idx + 1, cur - nums[idx]);
        }
    }

    public int findTargetSumWays2(int[] nums, int S) {
        int[] dp = new int[2001];
        dp[nums[0] + 1000] = 1;
        dp[-nums[0] + 1000] += 1;
        for (int i = 1; i < nums.length; i++) {
            int[] next = new int[2001];
            for (int sum = -1000; sum <= 1000; sum++) {
                if (dp[sum + 1000] > 0) {
                    next[sum + nums[i] + 1000] += dp[sum + 1000];
                    next[sum - nums[i] + 1000] += dp[sum + 1000];
                }
            }
            dp = next;
        }
        return S > 1000 ? 0 : dp[S + 1000];
    }
}
